/* Util.java
 * Miscellaneous helpful routines.
 * 
 * © 2007 David Given.
 *
 * $Id: Util.java 4 2007-06-25 15:26:37Z david.given $
 */

package com.cowlark.cowcalc;

public class Util
{
	/* Returns 10^i. */

	static long pow10(long i)
	{
		long n = 1;
		while (i > 0)
		{
			n *= 10;
			i--;
		}
		return n;
	}

	/* Calculates GCD of two longs. */

	static long gcd(long u, long v)
	{
		int shift;

		/* GCD(0,x) := x */
		if (u == 0 || v == 0)
			return u | v;

		/*
		 * Let shift := lg K, where K is the greatest power of 2 dividing both u
		 * and v.
		 */
		for (shift = 0; ((u | v) & 1) == 0; ++shift)
		{
			u >>= 1;
			v >>= 1;
		}

		while ((u & 1) == 0)
			u >>= 1;

		/* From here on, u is always odd. */
		do
		{
			while ((v & 1) == 0)
				/* Loop X */
				v >>= 1;

			/*
			 * Now u and v are both odd, so diff(u, v) is even. Let u = min(u,
			 * v), v = diff(u, v)/2.
			 */
			if (u < v)
			{
				v -= u;
			}
			else
			{
				long diff = u - v;
				u = v;
				v = diff;
			}
			v >>= 1;
		}
		while (v != 0);

		return u << shift;
	}

	static long add(long a, long b) throws OverflowException
	{
		if((a > 0 && b > Long.MAX_VALUE - a) || (a < 0 && b < Long.MIN_VALUE
		        - a))
			throw new OverflowException();
		return a+b;
	}
	
	static long mul(long a, long b) throws OverflowException
	{
		long result = a * b;
		if ((result / b) != a)
			throw new OverflowException();
		return result;
	}
}
